1. Field of the Invention
The present invention relates to computer systems and methods in which data resources are shared among concurrent data consumers while preserving data integrity and consistency relative to each consumer. More particularly, the invention concerns improvements to a mutual exclusion mechanism known as “read-copy update,” in which lock-free data read operations run concurrently with data update operations.
2. Description of the Prior Art
By way of background, read-copy update is a mutual exclusion technique that permits shared data to be accessed for reading without the use of locks, writes to shared memory, memory barriers, atomic instructions, or other computationally expensive synchronization mechanisms, while still permitting the data to be updated (modify, delete, insert, etc.) concurrently. The technique is well suited to multiprocessor computing environments in which the number of read operations (readers) accessing a shared data set is large in comparison to the number of update operations (updaters), and wherein the overhead cost of employing other mutual exclusion techniques (such as locks) for each read operation would be high. By way of example, a network routing table that is updated at most once every few minutes but searched many thousands of times per second is a case where read-side lock acquisition would be quite burdensome.
The read-copy update technique implements data updates in two phases. In the first (initial update) phase, the actual data update is carried out in a manner that temporarily preserves two views of the data being updated. One view is the old (pre-update) data state that is maintained for the benefit of operations that may be currently referencing the data. The other view is the new (post-update) data state that is available for the benefit of operations that access the data following the update. In the second (deferred update) phase, the old data state is removed following a “grace period” that is long enough to ensure that all executing operations will no longer maintain references to the pre-update data.
FIGS. 1A-1D illustrate the use of read-copy update to modify a data element B in a group of data elements A, B and C. The data elements A, B, and C are arranged in a singly-linked list that is traversed in acyclic fashion, with each element containing a pointer to a next element in the list (or a NULL pointer for the last element) in addition to storing some item of data. A global pointer (not shown) is assumed to point to data element A, the first member of the list. Persons skilled in the art will appreciate that the data elements A, B and C can be implemented using any of a variety of conventional programming constructs, including but not limited to, data structures defined by C-language “struct” variables.
It is assumed that the data element list of FIGS. 1A-1D is traversed (without locking) by multiple concurrent readers and occasionally updated by updaters that delete, insert or modify data elements in the list. In FIG. 1A, the data element B is being referenced by a reader r1, as shown by the vertical arrow below the data element. In FIG. 1B, an updater u1 wishes to update the linked list by modifying data element B. Instead of simply updating this data element without regard to the fact that r1 is referencing it (which might crash r1), u1 preserves B while generating an updated version thereof (shown in FIG. 1C as data element B′) and inserting it into the linked list. This is done by u1 acquiring a spinlock, allocating new memory for B′, copying the contents of B to B′, modifying B′ as needed, updating the pointer from A to B so that it points to B′, and releasing the spinlock. All subsequent (post update) readers that traverse the linked list, such as the reader r2, will thus see the effect of the update operation by encountering B′. On the other hand, the old reader r1 will be unaffected because the original version of B and its pointer to C are retained. Although r1 will now be reading stale data, there are many cases where this can be tolerated, such as when data elements track the state of components external to the computer system (e.g., network connectivity) and must tolerate old data because of communication delays.
At some subsequent time following the update, r1 will have continued its traversal of the linked list and moved its reference off of B. In addition, there will be a time at which no other reader process is entitled to access B. It is at this point, representing expiration of the grace period referred to above, that u1 can free B, as shown in FIG. 1D.
FIGS. 2A-2C illustrate the use of read-copy update to delete a data element B in a singly-linked list of data elements A, B and C. As shown in FIG. 2A, a reader r1 is assumed be currently referencing B and an updater u1 wishes to delete B. As shown in FIG. 2B, the updater u1 updates the pointer from A to B so that A now points to C. In this way, r1 is not disturbed but a subsequent reader r2 sees the effect of the deletion. As shown in FIG. 2C, r1 will subsequently move its reference off of B, allowing B to be freed following expiration of the grace period.
In the context of the read-copy update mechanism, a grace period represents the point at which all running processes having access to a data element guarded by read-copy update have passed through a “quiescent state” in which they can no longer maintain references to the data element, assert locks thereon, or make any assumptions about data element state. By convention, for operating system kernel code paths, a context (process) switch, an idle loop, and user mode execution all represent quiescent states for any given CPU (as can other operations that will not be listed here).
In FIG. 3, four processes 0, 1, 2, and 3 running on four separate CPUs are shown to pass periodically through quiescent states (represented by the double vertical bars). The grace period (shown by the dotted vertical lines) encompasses the time frame in which all four processes have passed through one quiescent state. If the four processes 0, 1, 2, and 3 were reader processes traversing the linked lists of FIGS. 1A-1D or FIGS. 2A-2C, none of these processes having reference to the old data element B prior to the grace period could maintain a reference thereto following the grace period. All post grace period searches conducted by these processes would bypass B by following the links inserted by the updater.
There are various methods that may be used to implement a deferred data update following a grace period, including but not limited to the use of callback processing as described in commonly assigned U.S. Pat. No. 5,727,209, entitled “Apparatus And Method For Achieving Reduced Overhead Mutual-Exclusion And Maintaining Coherency In A Multiprocessor System Utilizing Execution History And Thread Monitoring.” The contents of U.S. Pat. No. 5,727,209 are hereby incorporated herein by this reference.
The callback processing technique contemplates that an updater of a shared data element will perform the initial (first phase) data update operation that creates the new view of the data being updated, and then specify a callback function for performing the deferred (second phase) data update operation that removes the old view of the data being updated. The updater will register the callback function (hereinafter referred to as a “callback”) with a read-copy update subsystem so that it can be executed at the end of the grace period. The read-copy update subsystem keeps track of pending callbacks for each processor and monitors per-processor quiescent state activity in order to detect when each processor's current grace period has expired. As each grace period expires, all scheduled callbacks that are ripe for processing are executed.
The successful implementation of read-copy update requires efficient mechanisms for deducing the length of a grace period. One important class of implementations passes a grace period token from one processor to the next to signify that the end of a grace period has been reached for the processor owning the token. The grace period token can be a distinguished value that is expressly passed between processors. However, two memory write accesses are required when using this technique—one to remove the token from its current owner and another to pass the token to its new owner. A more efficient way of handling the grace period token is to pass it implicitly using per-processor quiescent state counters and associated polling mechanisms. According to this technique, whenever a processor passes through a quiescent state, its polling mechanism inspects the quiescent state counter of a neighboring processor to see if the neighbor's counter has changed since the current processor's last grace period. If it has, the current processor determines that a new grace period has elapsed since it last had the token. It executes its pending callbacks and then changes its quiescent state counter to an incrementally higher value than that of its neighbor. The next processor then sees this processor's changed counter value, processes its pending callbacks, and increments its own counter. This sequence continues, with the grace period token ultimately making its way through all of the processors in round-robin fashion.
Regardless of how the grace period token is implemented, each processor only processes callbacks when it receives the token. Insofar as the grace period token must travel through all other processors before reaching the processor that is the current holder, the current processor is always guaranteed that the other processors have passed through a quiescent state since the last time the current processor owned the token, thus ensuring that a grace period has elapsed.
Because grace period detection using token manipulation consumes processor cycles as the processors pass through their quiescent states, it is undesirable to incur such overhead unless there are pending callbacks in the read-copy update subsystem. For that reason, efficient token-based read-copy update implementations use a shared indicator (i.e., a global variable) that is tested before grace period token processing to determine if the read-copy update subsystem is idle. If it is, the grace period token does not need to be passed and the associated processing overhead can be avoided. The shared indicator is typically a count of the number of pending callbacks. Whenever a callback is registered at a given processor, the shared indicator is manipulated to reflect the new callback. Thereafter, when that callback is processed, the shared indicator is again manipulated to reflect the removal of the callback from the read-copy update subsystem.
A disadvantage of using a shared indicator to test for the existence of pending callbacks is that atomic instructions, locks or other relatively expensive mutual exclusion mechanisms must be invoked each time the shared indicator is manipulated in order to synchronize operations on the indicator by multiple processors. Moreover, conventional hardware caching of the shared indicator by each processor tends to result in communication cache misses and cache line bouncing. In the case of a bitmap indicator, a further disadvantage is that a large number of processors cannot be gracefully accommodated.
It is to solving the foregoing problems that the present invention is directed. In particular, what is required is a new read-copy update grace period detection technique that avoids unnecessary grace period token processing without incurring the overhead of a shared indicator of pending callback status.